#include <stdio.h>
#include <stdlib.h>

#define LH 1
#define EH 0
#define RH -1

#define TRUE 1
#define FALSE 0
// 平衡二叉树 AVL树
typedef struct balancedBinaryTree
{
    /* data */
    // 数据
    int a;
    // 平衡因子
    int bf;
    // 树高
    int treeHeight;
    struct balancedBinaryTree *left, *right;
} Tree;
// 初始化平衡树
Tree *BuildTree(int i)
{
    Tree *node = (Tree *)malloc(sizeof(Tree));
    if (NULL == node)
    {
        printf("err malloc");
        exit(-1);
    }
    node->a = i;
    node->bf = EH;
    node -> treeHeight = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}
// 插入元素
unsigned int insertAVL(Tree *node, int i)
{
    if (node->a > i)
    {
        if (node->left == NULL)
        {
            Tree *next = BuildTree(i);
            node->bf += LH;
            node->left = next;
        }
    }
    else if (node->a < i)
    {

    }
}

// 平衡树添加子元素
unsigned int maintenanceHeight(Tree *node, int i)
{
    if (node->a > i)
    {
        if (node->left == NULL)
        {
            Tree *next = BuildTree(i);
            node->bf += LH;
            node->left = next;
        }
        else
        {
            unsigned int f = maintenanceHeight(node->left, i);
            node->bf += f;
        }
    }
    else if (node->a < i)
    {
        if (node->right == NULL)
        {
            Tree *next = BuildTree(i);
            node->bf += RH;
            node->right = next;
        }
        else
        {
            unsigned int f = maintenanceHeight(node->right, i);
            node->bf -= f;
        }
    }
    if (node->bf > LH || node->bf < RH)
    {
        judgmentImbalanceTreeNode(node);
        return 0;
    }
    if (node->bf != EH)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
// 判断失衡节点 失衡状态
void judgmentImbalanceTreeNode(Tree *node)
{
    if (node->bf > LH)
    {
        if (node->left->bf == 1)
        {
            // 右旋 1
            rotationTree(node, 1);
        }
        else if (node->left->bf == -1)
        {
            // 先左旋再右旋 2
            rotationTree(node, 2);
        }
    }
    else if (node->bf < RH)
    {
        if (node->right->bf == 1)
        {
            // 先右旋再左旋 -1
            rotationTree(node, -1);
        }
        else if (node->right->bf == -1)
        {
            // 左旋 -2
            rotationTree(node, -2);
        }
    }
}
void leftRotation(Tree *top, Tree *next)
{
    // 平衡因子和树高 均欠缺
    // int bfCache = top->bf;

    Tree *topCache = top;
    *top = *next;

    if (next->left == NULL)
    {
        top->left = topCache;
        topCache->right = NULL;
    }
    else
    {
        top->left = topCache;
        topCache->right = next->left;
    }
    // topCache -> bf += bfCache;
}

void rightRotation(Tree *top, Tree *next)
{
    Tree *topCache = top;
    *top = *next;
    if (next->right == NULL)
    {
        top->right = topCache;
        topCache->left = NULL;
    }
    else
    {
        topCache->left = top->right;
        top->right = topCache;
    }
}
// 失衡旋转
void rotationTree(Tree *node, int i)
{
    switch (i)
    {
    case 1:
        /* code 右旋 */
        node->bf = EH;
        node->left = EH;
        rightRotation(node, node->left);
        break;
    case 2:
        /* code 先左旋再右旋 */
        leftRotation(node->left, node->left->right);
        rightRotation(node, node->left);
        break;
    case -1:
        /* code 先右旋再左旋*/
        rightRotation(node->right, node->right->left);
        leftRotation(node, node->right);
        break;
    case -2:
        /* code 左旋 */
        node->bf = EH;
        node->right = EH;
        leftRotation(node, node->right);
        break;
    default:
        break;
    }
}

// 遍历树
void ergodicTree(Tree *head)
{
    if (head == NULL)
    {
        return;
    }
    ergodicTree(head->left);
    ergodicTree(head->right);
    printf("%d\t", head->a);
}
// 释放资源
void freeTree(Tree *head)
{
    if (head == NULL)
        return;
    freeTree(head->left);
    freeTree(head->right);
    free(head);
    head = NULL;
}

int main()
{
    Tree *a = BuildTree(10);
    maintenanceHeight(a, 9);

    maintenanceHeight(a, 5);
    maintenanceHeight(a, 11);
    maintenanceHeight(a, 15);
    maintenanceHeight(a, 13);
    maintenanceHeight(a, 7);
    maintenanceHeight(a, 8);
    ergodicTree(a);
    printf("%d\n", a->bf);

    freeTree(a);
    a = NULL;
    return 0;
}